유한 상태 오토마톤

상태는 유한 상태 오토마톤이 취할 수 있는 모든 조건을 나타내는 추상적인 개념이다. 오토마톤은 특정 순간에 정확히 하나의 상태에 머물며, 이 상태는 시스템의 현재 상황이나 메모리를 요약한다. 예를 들어, 전등 스위치를 모델링하는 오토마톤은 '켜짐'과 '꺼짐'이라는 두 개의 상태를 가질 수 있다. 상태는 일반적으로 원이나 타원으로 표현되며, 그 안에 상태의 이름(예: q0, q1)이나 의미를 나타내는 라벨을 기재한다.

오토마톤의 상태는 유한 집합을 이룬다. 이는 상태의 총 개수가 한정되어 있음을 의미하며, '유한'이라는 이름의 근간이 된다. 상태의 수는 모델링하려는 시스템의 복잡도에 따라 달라진다. 간단한 자판기 모델은 몇 개의 상태만으로 구성될 수 있지만, 복잡한 통신 프로토콜이나 어휘 분석기를 모델링하는 오토마톤은 수십, 수백 개의 상태를 가질 수 있다.

상태는 시작 상태와 종결 상태라는 특별한 역할을 가질 수 있다. 시작 상태는 오토마톤이 입력 처리를 시작하는 초기 지점이다. 반면, 종결 상태는 입력 문자열이 오토마톤이 인식하는 형식 언어에 속한다고 판단될 때 도달하는 상태로, 일반적으로 이중 원으로 표시된다. 오토마톤의 동작은 시작 상태에서 출발하여 입력 심볼에 따라 다른 상태로 전이되며, 입력을 모두 소비한 후 종결 상태에 머물면 해당 입력을 '허용'한다.

알파벳은 유한 상태 오토마톤이 처리할 수 있는 모든 가능한 입력 심볼들의 유한 집합을 의미한다. 이는 오토마톤이 인식하거나 처리하는 언어의 기본 구성 요소를 정의하며, 보통 그리스 문자 시그마(Σ)로 표기된다. 예를 들어, 이진수를 처리하는 오토마톤의 알파벳은 {0, 1}이 될 수 있고, 영어 단어를 처리하는 경우 알파벳은 {a, b, ..., z}가 될 수 있다.

알파벳의 각 원소는 하나의 입력 심볼이며, 오토마톤은 이러한 심볼들로 구성된 문자열을 순차적으로 읽어 상태 전이를 일으킨다. 알파벳은 정규 언어를 정의하는 데 있어 핵심적인 역할을 하며, 정규 표현식에서 사용되는 문자들도 이 알파벳에서 비롯된다. 따라서 알파벳의 정의는 오토마톤이 어떤 범위의 입력을 처리할 수 있는지를 결정하는 첫 번째 단계이다.

전이 함수는 유한 상태 오토마톤이 현재 상태와 입력 심볼을 기반으로 다음 상태를 결정하는 규칙을 정의하는 핵심 구성 요소이다. 이 함수는 오토마톤의 동작 논리를 수학적으로 명시하며, 상태와 입력 알파벳 사이의 관계를 맵핑한다.

전이 함수는 일반적으로 δ(델타) 기호로 표기되며, 정의역은 현재 상태와 입력 심볼의 카르테시안 곱이고, 공역은 다음 상태의 집합이다. 결정적 유한 상태 오토마톤에서는 각 (상태, 입력) 쌍에 대해 정확히 하나의 다음 상태가 지정된다. 반면, 비결정적 유한 상태 오토마톤에서는 하나의 (상태, 입력) 쌍에 대해 여러 개의 다음 상태가 가능하며, 심지어 입력 없이도 전이가 가능한 엡실론 전이를 허용하기도 한다.

이 함수는 오토마톤이 특정 문자열이나 패턴을 인식하는 과정을 구동한다. 오토마톤은 시작 상태에서 출발하여 입력 문자열의 각 심볼을 순차적으로 읽으며, 전이 함수에 정의된 규칙에 따라 상태를 변경해 나간다. 문자열을 모두 읽은 후의 상태가 미리 정의된 종결 상태 집합에 속하면, 해당 입력 문자열은 오토마톤에 의해 "인식" 또는 "수용"된 것으로 간주된다.

유한 상태 오토마톤의 계산 과정은 항상 특정한 시작점에서 출발한다. 이 시작점이 바로 시작 상태이다. 시작 상태는 오토마톤이 입력 문자열을 처리하기 전에 초기화되어 위치하는 단일 상태를 의미한다. 모든 계산은 이 사전에 정의된 시작 상태에서부터 입력 심볼을 하나씩 읽으며 상태 전이를 시작하게 된다.

시작 상태는 오토마톤의 다섯 가지 구성 요소 중 하나로, 공식적으로 튜플 정의에 명시된다. 결정적 유한 상태 오토마톤과 비결정적 유한 상태 오토마톤 모두 정확히 하나의 시작 상태를 가진다. 이는 상태 다이어그램에서 보통 "시작"이라고 표기된 화살표가 가리키는 상태로 표현되며, 상태 전이표에서는 별도의 행이나 열로 구분되어 나타난다.

시작 상태는 반드시 종결 상태일 필요는 없다. 만약 입력 문자열이 빈 문자열(ε)이고, 시작 상태가 동시에 종결 상태라면, 해당 오토마톤은 빈 문자열을 인식하는 것으로 간주된다. 시작 상태의 설정은 오토마톤이 어떤 형식 언어를 인식하는지에 직접적인 영향을 미치는 핵심 매개변수이다.

종료 상태는 유한 상태 오토마톤이 입력 문자열을 모두 읽은 후 최종적으로 머무를 수 있는 상태들의 집합이다. 이는 시작 상태와 함께 오토마톤의 동작을 정의하는 핵심 구성 요소 중 하나이다. 오토마톤이 입력을 처리한 후 종료 상태 중 하나에 머물러 있어야 해당 입력 문자열을 "인식" 또는 "수용"한 것으로 간주한다. 따라서 종료 상태의 집합은 오토마톤이 인식하는 언어를 규정하는 데 결정적인 역할을 한다.

일반적으로 상태 다이어그램에서는 종료 상태를 이중 원으로 표시하여 시각적으로 구분한다. 예를 들어, 특정 패턴(예: "ab"로 끝나는 문자열)을 인식하는 오토마톤을 설계할 때, 해당 패턴이 완성된 시점에 해당하는 상태를 종료 상태로 지정한다. 오토마톤은 입력 심볼을 하나씩 읽으며 전이 함수에 따라 상태를 변경하다가, 입력 문자열이 끝났을 때 종료 상태 집합에 속한 상태에 도달하면 그 입력을 수용한다.

종료 상태는 하나 이상일 수 있으며, 경우에 따라서는 아예 존재하지 않을 수도 있다. 종료 상태가 없는 오토마톤은 어떤 입력 문자열도 수용하지 않는다는 것을 의미한다. 반대로, 모든 상태가 종료 상태인 오토마톤은 가능한 모든 입력 문자열을 수용하는 범용 오토마톤이 될 수 있다. 이러한 유연성 덕분에 정규 언어를 정확하게 정의하고 구별하는 모델로 널리 활용된다.

상태 다이어그램은 유한 상태 오토마톤의 구조와 동작을 시각적으로 표현하는 가장 일반적인 방법이다. 이는 유향 그래프의 형태로, 그래프의 정점은 오토마톤의 상태를, 간선은 상태 간의 전이를 나타낸다. 각 간선에는 해당 전이를 일으키는 입력 심볼이 레이블로 표시된다. 이 다이어그램을 통해 오토마톤이 특정 입력 문자열을 어떻게 처리하는지, 즉 시작 상태에서부터 입력을 하나씩 소비하며 상태를 어떻게 변화시키는지 직관적으로 이해할 수 있다.

상태 다이어그램에서 시작 상태는 보통 화살표가 없는 진입 간선으로 표시되며, 종결 상태는 이중 원으로 표시된다. 예를 들어, 상태 'q0'가 시작 상태이자 종결 상태라면, 'q0'는 이중 원으로 그려지고 진입 화살표가 함께 표시될 수 있다. 각 전이는 현재 상태에서 다음 상태로 향하는 화살표로 표현되며, 화살표 위에는 그 전이를 유발하는 입력 알파벳의 심볼이 적힌다. 비결정적 유한 상태 오토마톤의 경우, 동일한 입력 심볼에 대해 같은 상태에서 여러 개의 다른 상태로 나가는 간선이 존재할 수 있다.

이러한 시각적 표현은 정규 언어를 인식하는 오토마톤을 설계하거나 분석할 때 매우 유용하다. 설계자는 복잡한 시스템의 동작을 먼저 상태 다이어그램으로 스케치한 후, 이를 바탕으로 공식적인 전이 함수나 상태 전이표를 작성할 수 있다. 또한, 두 개의 오토마톤이 동등한지 검증하거나, 주어진 정규 표현식에 해당하는 오토마톤을 구성하는 과정에서도 상태 다이어그램은 핵심적인 도구로 활용된다.

상태 전이표는 유한 상태 오토마톤의 구조를 표 형태로 명확하게 표현하는 방법이다. 상태 다이어그램이 시각적이라면, 상태 전이표는 모든 전이 관계를 체계적으로 나열하여 기계의 동작을 명세적으로 정의하는 데 유용하다.

표는 일반적으로 행과 열로 구성된다. 행은 현재 상태를 나타내고, 열은 가능한 입력 심볼을 나타낸다. 각 셀에는 해당 현재 상태에서 주어진 입력 심볼을 받았을 때 전이되는 다음 상태가 기록된다. 결정적 유한 상태 오토마톤의 경우 각 셀에는 정확히 하나의 다음 상태가 명시되지만, 비결정적 유한 상태 오토마톤의 경우 하나의 셀에 여러 개의 다음 상태가 집합으로 기록될 수 있다.

위 표는 세 개의 상태(q0, q1, q2)와 두 개의 입력 심볼(a, b)을 가진 결정적 오토마톤의 예시이다. 예를 들어, 상태 q0에서 입력 a를 받으면 상태 q1으로 전이됨을 알 수 있다. 상태 전이표는 특히 상태와 입력의 개수가 많을 때, 또는 전이 함수를 프로그래밍적으로 구현할 때 유용한 참조 자료가 된다.

결정적 유한 상태 오토마톤은 가장 기본적이고 일반적인 유한 상태 오토마톤의 형태이다. 이 모델에서 주어진 현재 상태와 입력 심볼에 대해 다음 상태는 오직 하나로 정확히 결정된다. 즉, 전이 함수가 하나의 상태를 결과로 내놓는 함수이기 때문에, 동일한 입력 시퀀스에 대해 오직 하나의 경로만 존재한다. 이 결정성은 계산 이론에서 모델의 분석과 이해를 용이하게 만드는 핵심 특성이다.

DFA는 다섯 가지 구성 요소 (Q, Σ, δ, q0, F)로 공식적으로 정의된다. 여기서 Q는 유한한 상태들의 집합, Σ는 입력 알파벳, δ는 Q × Σ → Q 형태의 전이 함수, q0는 시작 상태, F는 종결 상태(또는 허용 상태)들의 집합이다. 이 모델은 주어진 입력 문자열을 처음부터 끝까지 순차적으로 읽으면서, 각 입력 심볼에 따라 전이 함수 δ에 정의된 대로 상태를 변경한다. 문자열을 모두 읽은 후의 상태가 F에 속하면 해당 문자열을 "허용" 또는 "인식"한다고 판단한다.

정규 표현식으로 표현 가능한 모든 정규 언어는 결정적 유한 상태 오토마톤으로도 인식할 수 있으며, 그 역도 성립한다. 이는 형식 언어 이론의 중요한 정리 중 하나이다. DFA의 결정적 특성 덕분에 주어진 언어를 인식하는 최소 상태의 DFA를 찾는 최소화 알고리즘이 존재하며, 이는 컴파일러의 어휘 분석기 생성 등 실용적인 도구 구현에 널리 활용된다.

비결정적 유한 상태 오토마톤(NFA)과 비교했을 때, DFA는 이론적으로 동등한 표현력을 가지지만, 일반적으로 동일한 언어를 인식하기 위해 더 많은 상태가 필요할 수 있다. 그러나 상태 전이가 명확하게 정의되어 있어 실제 소프트웨어나 하드웨어로 구현하기가 더 직관적이고 효율적이라는 장점이 있다.

비결정적 유한 상태 오토마톤은 결정적 유한 상태 오토마톤과 마찬가지로 유한 상태 기계의 한 종류이다. 결정적 오토마톤과의 핵심적 차이는, 주어진 현재 상태와 입력 심볼에 대해 다음 상태가 하나로 고정되지 않고, 여러 가능한 상태로 전이할 수 있다는 점에 있다. 즉, 전이 함수가 하나의 상태가 아닌 상태들의 집합을 결과로 반환한다. 또한 입력 심볼 없이 자발적으로 상태를 바꾸는 엡실론 전이를 허용하는 경우도 있다.

이러한 비결정성은 모델의 표현력을 높인다. 흥미롭게도, 비결정적 유한 상태 오토마톤이 인식할 수 있는 언어의 클래스는 결정적 유한 상태 오토마톤이 인식할 수 있는 언어의 클래스와 정확히 일치한다. 이는 정규 언어로 알려져 있으며, 모든 비결정적 오토마톤은 동등한 결정적 오토마톤으로 변환될 수 있다는 정리로 증명된다. 다만, 이 변환 과정에서 상태의 수가 기하급수적으로 증가할 수 있어, 모델을 설계할 때는 비결정적 오토마톤이 종종 더 간결하고 직관적인 표현을 제공한다.

비결정적 유한 상태 오토마톤은 정규 표현식을 오토마톤으로 변환하는 과정에서 자연스럽게 등장하며, 패턴 매칭 알고리즘이나 형식 언어 이론의 증명에서 유용하게 활용된다. 개념적으로는 여러 계산 경로를 동시에 탐색하는 병렬 계산 모델로 볼 수 있다. 오토마톤이 하나의 입력 문자열을 받아들일 때, 여러 가능한 경로 중 단 하나라도 최종 종결 상태에 도달하는 경로가 존재하면 그 입력을 인식한 것으로 본다.

컴파일러의 핵심 구성 요소 중 하나인 어휘 분석 단계에서 유한 상태 오토마톤은 필수적인 역할을 수행한다. 어휘 분석기는 소스 코드를 구성하는 문자열을 읽어서 토큰이라는 의미 있는 최소 단위로 분리하는 작업을 담당하는데, 이 과정에서 키워드, 식별자, 연산자, 리터럴 등과 같은 다양한 어휘소를 인식해야 한다. 이러한 어휘소의 패턴은 대부분 정규 언어로 표현 가능하며, 이를 인식하는 데 유한 상태 오토마톤이 효율적으로 사용된다.

예를 들어, 프로그래밍 언어에서 정수 리터럴을 인식하는 오토마톘은 숫자(0-9)로 시작하여 숫자만을 계속 읽는 상태와, 그 외의 문자를 만나면 종료 상태로 전이하는 간단한 구조를 가질 수 있다. 마찬가지로 식별자는 보통 알파벳 또는 밑줄로 시작하고, 그 뒤에 알파벳, 숫자, 밑줄이 올 수 있는 패턴을 가지며, 이는 해당하는 유한 상태 오토마톤으로 모델링된다. 컴파일러 제작 도구인 렉스나 플렉스는 개발자가 정규 표현식으로 어휘 규칙을 정의하면, 이를 내부적으로 유한 상태 오토마톤으로 변환하여 효율적인 어휘 분석기를 자동 생성한다.

이러한 방식으로 유한 상태 오토마톤을 사용함으로써, 컴파일러는 소스 코드를 빠르고 정확하게 토큰 스트림으로 변환할 수 있다. 이는 이후의 구문 분석 및 의미 분석 단계를 위한 기초를 제공하며, 전체 컴파일 과정의 효율성과 신뢰성을 높이는 데 기여한다.

유한 상태 오토마톤은 텍스트 검색 및 패턴 매칭 분야에서 핵심적인 역할을 한다. 특히, 특정 문자열이나 패턴을 효율적으로 찾아내는 알고리즘의 기반이 된다. 검색하고자 하는 패턴을 미리 유한 상태 오토마톤으로 구성해 두면, 긴 텍스트를 한 번만 훑으면서 모든 발생 위치를 빠르게 찾아낼 수 있다. 이 방식은 정규 표현식 엔진의 내부 구현에도 자주 활용된다.

유한 상태 오토마톤을 이용한 텍스트 검색의 대표적인 예는 KMP 알고리즘과 아호-코라식 알고리즘이다. KMP 알고리즘은 하나의 패턴을 검색할 때, 불일치가 발생해도 이미 비교한 정보를 활용해 효율적으로 재시작 위치를 결정하는데, 이 과정이 실질적으로 하나의 결정적 유한 상태 오토마톤을 구성하고 실행하는 것과 동일하다. 아호-코라식 알고리즘은 여러 개의 패턴을 동시에 검색하는 데 사용되며, 모든 패턴을 포함하는 하나의 트라이 구조를 확장한 유한 상태 오토마톤을 구축하여 검색을 수행한다.

이러한 방법론은 바이러스 백신 소프트웨어의 악성 코드 시그니처 검사, 텍스트 편집기의 찾기 기능, 데이터베이스의 풀텍스트 검색, 그리고 네트워크 침입 탐지 시스템에서 패턴 기반의 트래픽 분석 등 다양한 실제 응용 프로그램에 널리 적용된다. 유한 상태 오토마톤은 복잡한 패턴을 단순한 상태 전이로 표현함으로써 검색 과정을 체계화하고 성능을 최적화하는 강력한 도구를 제공한다.

유한 상태 오토마톤은 디지털 논리 회로와 순차 회로의 설계 및 모델링에 널리 활용된다. 특히, 시스템의 동작을 명확하게 정의하고 예측 가능하게 만드는 데 유용하다. 하드웨어 설계에서 유한 상태 오토마톤은 시스템이 가질 수 있는 모든 내부 상태와, 외부 입력에 따라 어떻게 상태가 바뀌는지를 기술하는 상태 머신으로 구현된다. 이는 복잡한 제어 흐름을 단순화하고, 설계 오류를 줄이는 데 기여한다.

구체적으로, 디지털 시계, 자동판매기, 엘리베이터 제어 시스템, 통신 프로토콜 컨트롤러 등 다양한 장치의 핵심 제어 유닛 설계에 적용된다. 예를 들어, 트래픽 신호등 제어기는 '빨강', '노랑', '초록'이라는 유한한 상태를 가지며, 타이머 신호라는 입력에 따라 정해진 순서대로 상태를 전이한다. 이러한 설계는 하드웨어 기술 언어를 이용해 논리 합성을 거쳐 실제 게이트 수준의 회로로 변환된다.

이러한 접근법은 설계의 정확성을 검증하고, 테스트 벤치 구축을 용이하게 하며, 다른 엔지니어와의 의사소통을 명확하게 한다. 결과적으로, 유한 상태 오토마톤은 복잡한 하드웨어 시스템을 체계적이고 신뢰성 있게 구현하는 데 필수적인 도구 역할을 한다.

프로토콜 설계 분야에서 유한 상태 오토마톤은 통신 프로토콜이나 네트워크 프로토콜의 동작을 명확하게 정의하고 검증하는 데 핵심적인 도구로 활용된다. 프로토콜은 두 개 이상의 개체 간 메시지 교환 순서와 규칙을 정의하는데, 이러한 상호작용의 흐름은 본질적으로 일련의 상태와 그 사이의 전이로 모델링할 수 있다. 예를 들어, 연결 설정, 데이터 전송, 연결 종료와 같은 프로토콜의 각 단계는 오토마톤의 특정 상태에 대응되며, 수신되는 메시지나 이벤트는 상태 간 전이를 유발하는 입력 역할을 한다.

이 모델링을 통해 설계자는 프로토콜의 동작을 시각적으로 표현하고, 상태 다이어그램이나 상태 전이표를 통해 명세의 모호성을 제거할 수 있다. 더 나아가, 유한 상태 오토마톤으로 표현된 프로토콜 모델은 특정 입력 시퀀스에 대해 예상치 못한 상태(예: 데드락 상태)에 도달하는지 여부와 같은 형식적 검증을 수행하는 데 사용될 수 있다. 이는 통신 시스템의 신뢰성과 안정성을 보장하는 데 중요한 과정이다.

따라서, 유한 상태 오토마톤은 복잡한 프로토콜의 논리를 체계적으로 설계, 분석, 구현하는 표준적인 방법론을 제공하며, 특히 임베디드 시스템이나 네트워크 장비의 펌웨어 개발에서 널리 적용되는 개념이다.

정규 표현식은 문자열의 패턴을 기술하는 데 사용되는 형식 언어이다. 유한 상태 오토마톤과 밀접한 관계를 가지며, 정규 언어를 표현하는 가장 일반적인 방법 중 하나이다. 즉, 모든 정규 표현식은 그에 상응하는 유한 상태 오토마톤으로 변환될 수 있으며, 그 반대도 가능하다. 이는 형식 언어 이론의 중요한 정리 중 하나로, 정규 언어의 인식 능력이 유한 상태 오토마톤과 정규 표현식이 동등함을 보여준다.

정규 표현식은 기본 연산자인 합집합, 연접, 클레이니 스타를 조합하여 복잡한 패턴을 구성한다. 예를 들어, 'a'로 시작하고 'b'로 끝나는 모든 문자열은 정규 표현식 a.*b로 나타낼 수 있다. 이러한 패턴은 유한 상태 오토마톤을 통해 효율적으로 인식되며, 이는 컴파일러의 어휘 분석 단계나 텍스트 검색 도구에서 널리 활용된다.

이러한 동등성 덕분에 정규 표현식으로 정의된 패턴 매칭 문제는 내부적으로 비결정적 유한 상태 오토마톤 또는 결정적 유한 상태 오토마톤으로 변환되어 처리된다. 이는 계산 이론의 개념이 프로그래밍 언어와 소프트웨어 도구에 실용적으로 적용되는 대표적인 사례이다.

정규 언어는 형식 언어 이론에서 가장 기본적인 언어 계층 중 하나로, 유한 상태 오토마톤에 의해 인식될 수 있는 언어의 집합을 가리킨다. 이는 정규 표현식으로 완전히 기술될 수 있으며, 두 개념은 클레이니 정리에 의해 동등함이 증명되어 있다. 즉, 모든 정규 언어는 정규 표현식으로 표현 가능하고, 그 역도 성립한다.

정규 언어는 계산 이론에서 촘스키 위계의 가장 낮은 단계에 위치하며, 결정적 유한 상태 오토마톤과 비결정적 유한 상태 오토마톤 모두에 의해 수용된다. 이 언어 계층은 합집합, 접합, 클레이니 스타 연산과 같은 정규 연산에 대해 닫혀 있는 특성을 가진다. 이러한 폐쇄성 덕분에 정규 언어는 수학적으로 다루기 쉬운 구조를 지닌다.

주요 응용 분야로는 컴파일러의 어휘 분석 단계에서 프로그래밍 언어의 토큰(예: 식별자, 숫자 리터럴, 연산자)을 인식하는 데 사용된다. 또한 텍스트 검색과 패턴 매칭에서 문자열 내 특정 패턴을 찾는 정규 표현식 엔진의 기초가 되며, 프로토콜 설계나 하드웨어 설계에서 시스템의 유한한 상태 변화를 모델링하는 데도 활용된다.

정규 언어보다 더 복잡한 언어 계층으로는 문맥 자유 언어가 있으며, 이는 푸시다운 오토마톤에 의해 인식된다. 반면, 정규 언어로 표현할 수 없는 간단한 패턴도 존재하는데, 대표적인 예가 균형 잡힌 괄호 문자열이다. 이는 유한 상태 기계가 임의의 깊이를 기억할 수 없기 때문이다.

푸시다운 오토마톤(PDA)은 유한 상태 오토마톤의 한계를 극복하기 위해 고안된 계산 모델이다. 유한 상태 오토마톤이 정규 언어만을 인식할 수 있는 반면, 푸시다운 오토마톤은 스택이라는 무한한 메모리 구조를 추가하여 문맥 자유 언어를 인식할 수 있다. 이는 괄호의 짝 맞추기나 특정한 패턴의 중첩 구조를 처리하는 데 필수적이다.

푸시다운 오토마톤의 구성 요소는 유한 상태 오토마톤의 구성 요소에 스택을 조작하는 기능이 추가된다. 핵심은 전이 함수가 현재 상태, 입력 심볼, 그리고 스택의 최상위 심볼에 따라 다음 상태와 스택에 수행할 동작(푸시 또는 팝)을 결정한다는 점이다. 이를 통해 기억 장치 역할을 하는 스택을 이용해 더 복잡한 언어를 처리할 수 있게 된다.

푸시다운 오토마톤은 정규 표현식으로 표현할 수 없는 언어를 다루는 데 핵심적이며, 컴파일러의 구문 분석 단계에서 널리 응용된다. 특히 프로그래밍 언어의 문법, 대부분이 문맥 자유 문법에 속하기 때문에, 이를 처리하는 파서의 이론적 기반이 된다. 이 모델은 형식 언어 이론에서 유한 상태 오토마톤과 튜링 기계 사이의 중요한 계산 능력 계층을 구성한다.